package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 交错字符串
    static class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            // 1) 边界处理
            int n = s1.length();
            int m = s2.length();
            if(n + m != s3.length()) return false;

            // 2) 添加占位符，避免索引转换
            String _s = " " + s1;
            String _p = " " + s2;
            String _x = " " + s3;

            char[] s = _s.toCharArray();
            char[] p = _p.toCharArray();
            char[] x = _x.toCharArray();

            boolean[][] dp = new boolean[n+1][m+1];

            // 3) 初始化第一列：只使用s1
            for(int i = 1; i <= n; i++){
                if(s[i] == x[i]) dp[i][0] = true;
                else break;
            }

            // 4) 初始化第一行：只使用s2
            for(int i = 1; i <= m; i++){
                if(p[i] == x[i]) dp[0][i] = true;
                else break;
            }
            dp[0][0] = true;

            // 5) 动态规划填表
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    boolean a = false, b = false;
                    if(s[i] == x[i+j]){  // 从s1取字符
                        a = dp[i-1][j];
                    }
                    if(p[j] == x[i+j]){  // 从s2取字符
                        b = dp[i][j-1];
                    }
                    dp[i][j] = a || b;   // OR逻辑
                }
            }

            // 6) 返回最终结果
            return dp[n][m];
        }
    }
}